package hot100.字符串异位词;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author llt
 * @date 2025/6/16
 */
public class Test {
    /**
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     */
    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<>();
        }

        ArrayList<Integer> list = new ArrayList<>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];

        // 初始化第一个窗口
        for (int i = 0; i < pLen; i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }

        // i表示窗口外（右边）第一个元素位置
        for (int i = pLen; i <= sLen; i++) {
            // 检查前一个窗口是否想等
            if (Arrays.equals(sCount, pCount)) {
                list.add(i - pLen);
            }
            // 滑动窗口，去掉s左边字符，添加右边字符
            if (i < sLen) {
                sCount[s.charAt(i - pLen) - 'a']--;
                sCount[s.charAt(i) - 'a']++;
            }

        }

        return list;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        findAnagrams(s, p);
    }
}
